package 栈和队列;

/**
 * @description: 双端队列
 * @author: ywk
 * @date: 2020-06-28
 */
public class DoubleHeadQueue implements Cloneable {
    int[] data;
    int front;
    int back;

    public DoubleHeadQueue() {
    }

    public DoubleHeadQueue(int[] arr) {
        this.data = arr;
        front = 0;
        back = arr.length - 1;
    }

    public int popFront() {
        int val = data[front];
        int[] dest = new int[data.length - 1];
        System.arraycopy(data, 1, dest, 0, dest.length);
        this.back = dest.length - 1;
        this.data = dest;
        return val;
    }

    public int popBack() {
        int val = data[back];
        int[] dest = new int[data.length - 1];
        System.arraycopy(data, 0, dest, 0, dest.length);
        this.back = dest.length - 1;
        this.data = dest;
        return val;
    }

    public void pushFront(int val) {
        int[] dest;
        if (this.isEmpty()) {
            data = new int[1];
            dest = data;
        } else {
            dest = new int[data.length + 1];
        }
        System.arraycopy(data, 0, dest, 1, data.length);
        this.back = dest.length - 1;
        dest[front] = val;
        this.data = dest;
    }

    public void pushBack(int val) {
        int[] dest;
        if (this.isEmpty()) {
            data = new int[1];
            dest = data;
        } else {
            dest = new int[data.length + 1];
        }
        System.arraycopy(data, 0, dest, 0, data.length);
        this.back = dest.length - 1;
        dest[back] = val;
        this.data = dest;
    }

    public int getFront() {
        return data[front];
    }


    public int getBack() {
        return data[back];
    }

    public boolean isEmpty() {
        if (data == null) {
            return true;
        }
        return data.length == 0 ? true : false;
    }

    public void disPlay() throws CloneNotSupportedException {
        DoubleHeadQueue queue = new DoubleHeadQueue();
        queue = (DoubleHeadQueue) this.clone();
        while (!queue.isEmpty()) {
            System.out.println(queue.popBack());
        }
    }

    @Override
    protected Object clone() throws CloneNotSupportedException {
        return super.clone();
    }

    void MaxSlidingWindow(int A[], int w, int B[]) {
        DoubleHeadQueue queue = new DoubleHeadQueue();
        for (int i = 0; i < w; i++) {
            while (!queue.isEmpty() && A[i] >= A[queue.getBack()]) {
                queue.popBack();
            }
            queue.pushBack(i);
        }
        for (int i = w; i < A.length; i++) {
            B[i - w] = A[queue.getFront()];
            //存储最大值的坐标
            //新来的元素大于最后一个，
            while (!queue.isEmpty() && A[i] >= A[queue.getBack()]) {
                queue.popBack();
            }
            //该最大值坐标不在窗口中
            while (!queue.isEmpty() && queue.getFront() <= i - w) {
                queue.popFront();
            }
            queue.pushBack(i);
        }
        B[A.length - w] = A[queue.getFront()];
        for (int i : B) {
            System.out.println(i);
        }
    }


    public static void main(String[] args) throws CloneNotSupportedException {
        DoubleHeadQueue queue = new DoubleHeadQueue(new int[]{1, 2, 3, 4, 5});
        DoubleHeadQueue test = new DoubleHeadQueue();
        //最大滑动窗口
        test.MaxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3, new int[6]);


    }
}
